# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/14 16:44
功能描述:
题目背景：
    你正在管理一个高性能计算集群，有许多研究项目提交了计算任务。每个任务都有一个开始时间和一个结束时间。由于计算资源有限，你无法同时运行时间重叠的任务。为了最大化集群的利用率，你需要选择一个任务子集，使得这个子集中的任务数量最多，且任务之间互不重叠。
任务描述：
    设计一个 Task 类来表示一个计算任务，包含 name , start_time , end_time 属性。
    然后实现一个函数 max_tasks_schedule(tasks) ，该函数接收一个 Task 对象列表，返回一个最优的任务调度方案（一个Task对象列表），使得被调度的任务数量最多。请使用面向对象的思想来组织数据并解决问题。

输出结果是一个列表，顺序可能不同，但内容和数量应一致

"""
#用于从标准库的 typing 模块中导入 List 类型，主要作用是提供类型提示（Type Hints），帮助开发者和工具（如 IDE、静态检查工具）理解函数参数、返回值或变量的预期类型，提升代码的可读性和可维护性。
from typing import List

class Task:
    def __init__(self, name: str, start_time: int, end_time: int):
        self.name = name
        self.start_time = start_time
        self.end_time = end_time

    def __repr__(self):
        return f"Task(name='{self.name}', start={self.start_time}, end={self.end_time})"


def max_tasks_schedule(tasks: List[Task]) -> List[Task]:
    """
    接收一个任务列表，返回一个最大数量的、互不重叠的任务调度方案。
    贪心策略：按结束时间对任务进行排序。总是选择第一个结束的任务，然后从剩余任务中选择与已选任务不冲突的、结束时间最早的任务。
    """
    if not tasks:
        return []
    # 1. 使用对象的属性进行排序，体现OOP的便利性
    # 按结束时间对所有任务进行升序排序
    sorted_tasks = sorted(tasks, key=lambda task: task.end_time)
    # 2. 执行贪心算法
    schedule = []
    # 第一个任务总是被选中
    schedule.append(sorted_tasks[0])
    last_task_end_time = sorted_tasks[0].end_time
    for i in range(1, len(sorted_tasks)):
        current_task = sorted_tasks[i]
        # 如果当前任务的开始时间晚于或等于上一个被选中任务的结束时间
        if current_task.start_time >= last_task_end_time:
            schedule.append(current_task)
            last_task_end_time = current_task.end_time
    return schedule

# ---- 测试代码 ----
tests = [
    [],
    [Task('A', 1, 3)],
    [Task('A', 1, 4), Task('B', 2, 5), Task('C', 5, 7)],
    [Task('A', 9, 11), Task('B', 8, 10), Task('C', 10, 12)],
    [Task('A', 1, 2),      Task('B', 3, 4),     Task('C', 0, 6),     Task('D', 5, 7),      Task('E', 8, 9),     Task('F', 5, 9)],
    [Task('A', 1, 10), Task('B', 2, 3), Task('C', 4, 5), Task('D', 6, 7)]
]

for test_tasks in tests:
    result = max_tasks_schedule(test_tasks)
    print(f"{[t.name for t in result]}")

"""
[]
['A']
['A', 'C']   #没有B，是因为B的开始时间已经错过了
['B', 'C'] # 同理 没有A，是因为B执行结束后，已经是10点了 已经超过了A的开始时间(9点) A已经无法获得执行机会了
['A', 'B', 'D', 'E']
['B', 'C', 'D']
"""



"""
1:from typing import List

在 Python 中，from typing import List 用于从标准库的 typing 模块中导入 List 类型，主要作用是提供类型提示（Type Hints），帮助开发者和工具（如 IDE、静态检查工具）理解函数参数、返回值或变量的预期类型，提升代码的可读性和可维护性。
具体用途：
List 是一个泛型类型（Generic Type），用于指定 “列表中元素的类型”。例如：

from typing import List
# 提示函数参数 `nums` 是一个整数列表，返回值是一个整数列表
def process_numbers(nums: List[int]) -> List[int]:
    return [x * 2 for x in nums]
这里：
List[int] 表示 “元素类型为 int 的列表”；
类型提示不会影响代码的运行（Python 是动态类型语言，运行时不强制检查类型），但能让 IDE（如 PyCharm、VS Code）提供更精准的自动补全、错误提示（例如这里传入字符串列表时会警告）。
为什么需要 List 而非直接用 list？
在 Python 3.9 之前，内置类型 list 无法直接指定元素类型（例如 list[int] 是不合法的），必须使用 typing.List 来表示 “元素类型明确的列表”。
Python 3.9 及以上版本引入了标准集合的泛型支持，可以直接用 list[int] 替代 List[int]，因此：
3.9+ 版本：list[int] 和 typing.List[int] 功能等价；
3.9 之前版本：必须用 typing.List[int] 才能指定元素类型。
类似的类型提示工具：
typing 模块还提供了其他常用泛型类型，例如：

Tuple：指定元组元素类型（如 Tuple[str, int] 表示 “第一个元素为字符串，第二个为整数的元组”）；
Dict：指定字典的键值类型（如 Dict[str, float] 表示 “键为字符串、值为浮点数的字典”）；
Set：指定集合元素类型（如 Set[int] 表示 “整数集合”）；
Optional：表示变量可以是指定类型或 None（如 Optional[str] 等价于 Union[str, None]）。

总结：
from typing import List 是为了在代码中使用 List 进行列表元素的类型提示，尤其在 Python 3.9 之前的版本中是必需的。它的核心价值是增强代码的可读性和工具支持，而非强制类型检查。如果使用 Python 3.9+，也可以直接用 list[int] 替代。


"""